from MultiNode import MultiNode, print_mnode, print_instance
from Pastor import print_pop
from Pastor import roulette
import copy
import logging
import logging.handlers
import random

class SuperGraph:
    
    LOG_FILENAME = 'supergraph.log'
    # Set up a specific logger with our desired output level
    logger = logging.getLogger('supergraph')
    logger.setLevel(logging.DEBUG)
    handler = logging.handlers.RotatingFileHandler(LOG_FILENAME, maxBytes=200000, backupCount=5)
    logger.addHandler(handler)
    
    def __init__(self, name=''):
        self.name = name
        self.multinodes = {} #<name, multinode>
    
    def add_edge(self, origin, destination, payload, instance): #payload is GenEdge
        """
        adds a new edge to the graph. 
        """
        
        if origin not in self.multinodes: # if origin is not in the graph
            multinode = MultiNode(origin) # create a new multinode
            multinode.add_edge(destination, payload, instance) # add the edge to the multinode
            self.multinodes[origin] = multinode # set multinode to key
        else:
            self.multinodes[origin].add_edge(destination, payload, instance) # origin already in graph. just add the edge
    
    def remove_node(self, node): 
        del self.multinodes[node]
    
    def edges_iter(self):
        return self.multinodes.iter

    def combine(self, new_graph, eq_table):
        """
        combines the new_graph with this graph, then repairs it using the eq_table
        """
        self.logger.debug("START COMBINE")
        
        self.logger.debug("SELF:")
        for mnode in self.multinodes.values():
            self.logger.debug(print_mnode(mnode))
        self.logger.debug("INCOMING:")
        for mnode in new_graph.multinodes.values():
            self.logger.debug(print_mnode(mnode))
            
        self.logger.debug("TABLE:\n" + print_dict(eq_table))
        for node in new_graph.multinodes.keys(): # for each node in the new graph to combine <String>
            self.logger.debug("NODE: " + str(node))
            try:
                eq_node = eq_table[node] # get correspondent node from table
            except KeyError: # if not in keys must be in values
                try:
                    reverse_table = dict([(v, k) for (k, v) in eq_table.iteritems()]) # switch table
                    eq_node = reverse_table[node] # try again
                except KeyError:
                    eq_node = "DUMMY_NODE_XYZ"
            
            if eq_node not in self.nodes(): # if correspondent node not in this graph
                self.logger.debug("COPY WHOLE " + str(node))
                self.multinodes[node] = copy.deepcopy(new_graph[node]) # copy the whole multinode
            else:   # if correspondent node already in this graph
                self.logger.debug("COPY INSTANCE: " + str(node))
                for instance in new_graph[node].instance_list(): # for each instance of the new node
                    try:
                        node_to_update = self.multinodes[eq_table[node]] # get the correspondent node from table <Multinode>
                    except KeyError:
                        reverse_table = dict([(v, k) for (k, v) in eq_table.iteritems()])
                        node_to_update = self.multinodes[reverse_table[node]]
                        
                    node_to_update.instances[node_to_update.next_instance()] = copy.deepcopy(new_graph[node][instance])  # update the node with new node instance
        self.repair(eq_table) # repair the graph
    
    def repair(self, eq_table):
        """
        run through the graph edges repairing misconnections when necessary using the lookup table
        """
        self.logger.debug("START REPAIR. GRAPH:")
        for mnode in self.multinodes.values():
            self.logger.debug(print_mnode(mnode))    
        #self.start
        for node in self.multinodes.values(): # for each node in graph <Multinode>
            self.logger.debug("NODE: " + print_mnode(node))
            for instance in node.instances.values(): # for each instance of node <String>
                self.logger.debug("INSTANCE:\n" + print_instance(instance))
                for edge in instance: # for each edge in instance <List>
                    self.logger.debug("EDGE: " + str(edge[0]))
                    if edge[0] not in self.multinodes.keys(): # if destination not in graph's nodes
                        self.logger.debug("CONFLICT: " + str(edge[0]))
                        destination = edge[0] # get destination
                        if (not destination == "SQUARE") and (not destination == "CIRCLE"): # if destination not  terminal.
                            try:
                                edge[0] = eq_table[destination] # retrieve correspondent node from table and update edge
                            except KeyError: # if not in the keys, it must be in the values
                                try:
                                    reverse_table = dict([(v, k) for (k, v) in eq_table.iteritems()]) # switch keys for values
                                    edge[0] = reverse_table[destination] # try again
                                except KeyError:
                                    if roulette(40):
                                        edge[0] = random.choice(self.multinodes.keys())
                                    else:
                                        edge[0] = random.choice(["SQUARE", "CIRCLE"])
        
    def excise(self, to_excise):
        """
        excises the given subgraph from this graph for purposes of readying the parent to receive the mate's subgraph.
        """
        for target in to_excise:
            if len(self.multinodes[target[0]].instance_list()) == 1: # if target node contains only one instance,
                self.remove_node(target[0]) # remove it.
            else:
                self.multinodes[target[0]].remove_instance(target[1]) # else, remove target instance.
    
    def subgraph(self, node, max_instances, max_distance):
        """
        extract a subgraph with epicenter on node with max_instances per node
        and max_distance level neighbours
        """
        subgraph = SuperGraph()
        to_excise = []
        to_excise = self.get_neighbours(node, subgraph, max_distance, to_excise)
        
        self.logger.debug("SELF:\n" + self.print_graph())
        self.logger.debug("TO EXCISE: " + str(set(to_excise)))
        
        self.excise(set(to_excise)) # clear parent of the xover material      
        return subgraph
    
    def get_neighbours(self, mnode, subgraph, distance, to_excise):
        self.logger.debug("----------------- GET NEIGHBOURS")
        if (distance == 1) or (mnode == "CIRCLE") or (mnode == "SQUARE"): # stop condition
            self.logger.debug("distance 1, returning... in " + str(mnode))
            return to_excise
        self.logger.debug("node: " + str(mnode) + ", distance: " + str(distance))
        
        if mnode not in subgraph.nodes(): #if the current node doesn't yet exist in the subgraph
            subgraph[mnode] = MultiNode(mnode)
            
        instance = subgraph[mnode].next_instance() # get next usable instance <String>
        
        self.logger.debug("instance " + str(instance))
        original_instance = self.multinodes[mnode].get_random_instance() # get a random instance. return is a list containing the proper instance [0] and it's name [1]
        subgraph[mnode].instances[instance] = original_instance[0]
        
        to_excise.append((mnode, original_instance[1])) # keep current node/instance information for excising purposes 
        
        self.logger.debug("TO_EXCISE: " + str(to_excise))       
        self.logger.debug("neighbours: " + str(self.multinodes[mnode].neighbours(original_instance[1])))
        
        for n in set(self.multinodes[mnode].neighbours(original_instance[1])): #for each neighbour of mnode.instance -> wrapped with set() to get rid of duplicates
            self.logger.debug("neighbour: " + n)
            to_excise.extend(self.get_neighbours(n, subgraph, distance - 1, to_excise)) # recursively call get_neighbours with distance - 1
        return to_excise
    
    def neighbours(self, node, instance):
        return self.multinodes[node].neighbours(instance)  
    
    def __str__(self):
        return self.name
    
    def nodes(self):
        return self.multinodes.keys()    

    def nodes_iter(self):
        return self.multinodes.iterkeys()
        """
        Allows the expression 'n in G'.
        Testing whether an unhashable object, such as a list, is in the
        dict datastructure (self.adj) will raise a TypeError.
        Rather than propagate this to the calling method, just
        return False.
        """
        try:
            return n in self.multinodes
        except TypeError:
            return False
    
    def __getitem__(self, n):
        """Return the neighbors of node n as a list.
        This provides graph G the natural property that G[n] returns
        the neighbors of G. 
        """
        try:
            return self.multinodes.get(n)
        except KeyError:
            raise GraphError, "node %s not in graph" % (n,)
    
    def __setitem__(self, key, item):
        """
        sets the <key> in the graph to map <item>
        provides the property -> G[key] = item
        """
        self.multinodes[key] = item
    
    def print_graph(self):
        ret = ""
        for mnode in self.multinodes.values():
            ret += print_mnode(mnode)
        return ret
    
    def bfs(self, start, graph):
        "breadth-first traversing of the graph for purposes of building a lookup table"
        queue = []
        list = []
        queue.append(start)
        node = start
        while len(queue) > 0: # while queue not empty           
            node = queue.pop(0) # pop queue
            if node == "SQUARE" or node == "CIRCLE": # terminal symbols. end.
                return list
            if node not in list: #if node not visited
                list.append(node) # append to list
            mnode = graph[node] # get the multinode
            for instance in mnode.instance_list(): # for each instance in multinode
                for neighbour in set(graph[node].neighbours(instance)): # for each unique neighbour in the instance
                    queue.append(neighbour) #append to list
        self.logger.debug("bfs table: " + str(list))
        return list
    
def print_dict(dict):
    ret = ""
    for k, v in dict.items():
        ret += "    " + str(k) + " : " + str(v) + "\n"
    return ret
